package com.dmall.play.interview.chapter07;

public class Leetcode450V2 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    '}';
        }
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
            return root;
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
            return root;
        } else {
            if (root.left == null && root.right == null) {
                return null;
            } else if (root.right != null) {
                TreeNode successor = successor(root);
                successor.right = deleteNode(root.right, successor.val);
                successor.left = root.left;
                root.left = root.right = null;
                return successor;
            } else {
                TreeNode precursor = precursor(root);
                precursor.left = deleteNode(root.left, precursor.val);
                precursor.right = root.right;
                root.left = root.right = null;
                return precursor;
            }
        }
    }

    private TreeNode successor(TreeNode node) {
        TreeNode successor = node.right;
        while (successor.left != null) {
            successor = successor.left;
        }
        return successor;
    }

    private TreeNode precursor(TreeNode node) {
        TreeNode precursor = node.left;
        while (precursor.right != null) {
            precursor = precursor.right;
        }
        return precursor;
    }
}
